#include <stdio.h>
#include <stdlib.h>

typedef struct binaryTree
{
    char c;
    struct binaryTree *left;
    struct binaryTree *right;

} BinaryTree;

typedef struct stack
{
    struct binaryTree *data[13];
    int top;
} Stack;

BinaryTree *createTree(int index, int size);
void printFrontTree(BinaryTree *root);
void printMiddleTree(BinaryTree *root);
void printLastTree(BinaryTree * root);
void levelTraversal(BinaryTree * root);

int main()
{
    BinaryTree *root = createTree(0, 13);
    printf("先序遍历：根左右\n");
    printFrontTree(root);
    printf("\n");
    printf("中序遍历：左根右\n");
    printMiddleTree(root);
    printf("\n");
    printf("后序遍历：左右根\n");
    printLastTree(root);
    printf("\n");
    printf("层序遍历：\n");
    levelTraversal(root);
}

void levelTraversal(BinaryTree * root){
	BinaryTree * q[100];
	q[0] = root;
	int front = 0;
	int rear = 1;
	while(front < rear){
		printf("%c",q[front]->c);
		if(q[front]->left)
		{
			q[rear++] = q[front]->left;
		}	
		if(q[front]->right){
			q[rear++] = q[front]->right;
		}

		++front;
	}
}
BinaryTree *createTree(int index, int size)
{
    char s[] = {'I', ' ', 'L', 'O', 'V', 'E', ' ', 'C', 'H', 'I', 'N', 'A', '!'};
    BinaryTree *node = (BinaryTree *)malloc(sizeof(BinaryTree));
    if (index < size)
    {
        node->c = s[index];
        node->left = createTree(index * 2 + 1, 13);
        node->right = createTree(index * 2 + 2, 13);
    }
    else
    {
        node = NULL;
    }
    return node;
}

void printFrontTree(BinaryTree *root)
{
    if (root != NULL)
    {
        printf("%c", root->c);
        printFrontTree(root->left);
        printFrontTree(root->right);
    }
}
void printMiddleTree(BinaryTree *root)
{
    if (root != NULL)
    {
        printMiddleTree(root->left);
        printf("%c", root->c);
        printMiddleTree(root->right);
    }
}

void printLastTree(BinaryTree * root)
{
    Stack stack;
    BinaryTree *temp = root;
    int flag[13];
    stack.top = 0 ;
    while (stack.top!=0||temp)
    {
        
        while (temp)
        {
            stack.data[stack.top++] = temp;
            flag[stack.top-1] = 0;
            temp = temp->left;
        }

        while (stack.top!=0 && flag[stack.top - 1] == 1)
        {
            temp = stack.data[--stack.top];
            printf("%c",temp->c);
        }

        if(stack.top != 0)
        {
            flag[stack.top - 1] = 1;
            temp = stack.data[stack.top - 1];
            temp = temp->right;
        }else
        {
            break;
        }
        
        
        
    }
    
}
